A three-dimensional database controls a set of objects positioned in a spatiotemporal space. For example, the objects are three-dimensional (3D) objects of application software such as GIS or CAD. The three-dimensional database has a function to accept a query indicating a range and return a list of objects included in the range. As a data structure/index of the database, R-tree, Quad-tree, or expansion thereof, are used.
As conventional technique, a function to decide invention/collision by using a quadric surface is known. As to this function, a quadric surface approximating an object (represented as a polyhedron) is generated, and collision decision is simply performed by using the quadric surface. In this case, parts (components) in a machine densely including at largest 10000 parts are decided whether to collide. This technique does not attach importance to accuracy of approximation, and each part is very roughly approximated as a minimum bounded box. On the other hand, in order to quickly decide whether to collide with a quadric surface (indicated), decision steps are finely controlled.
Furthermore, as a thesis thereof, R-tree (Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching, Proc. 1984 ACM SIGMOD International Conference on Management of Data, pp. 47-57. ISBN 0-89791-128-8), and Quad-tree (Raphael Finkel and J. L. Bentley (1974), “Quad Trees: A Data Structure for Retrieval on Composite Keys”, Acta Informatica 4 (1): doi:10.1007/BF00288933), are well known. In these theses, a data structure to process a large number (such as a million units) of objects is disclosed. However, a region indicated by a query is only a rectangle. Accordingly, the query cannot be finely controlled such as a quadric surface.
Briefly, in R-tree and Quad-tree, each object is controlled as a unit of minimum bounded box (MBB) surrounding the object, and a region indicated by the query is also a cuboid.
However, in 3D database to control position (location) of a PV (Photovoltaic power generation) device (panel), a query such as a list of objects (PV panel) included in a shadow of a building, a list of objects included in a view from some viewpoint, or a list of objects inside a circle having a radius of n km from the indicated point, is often generated.